package com.yanceysong.codetop.s41_s50;

public class S42_Easy_704_二分查找 {
    /**
     * LeetCode 704. Binary Search
     * 题目链接: <a href="https://leetcode.cn/problems/binary-search/">...</a>
     * ------------------------------------------------------------
     * 题目描述:
     * 给定一个 升序 排序的整型数组 nums (长度 n) 和一个目标值 target, 在其中用 O(log n) 时间复杂度查找 target。
     * 如果找到则返回其下标, 否则返回 -1。
     * ------------------------------------------------------------
     * 示例:
     * 输入: nums = [-1,0,3,5,9,12], target = 9  -> 输出: 4 (nums[4] == 9)
     * 输入: nums = [-1,0,3,5,9,12], target = 2  -> 输出: -1 (不存在)
     * ------------------------------------------------------------
     * 核心洞察 (Key Insights):
     * 1. 二分查找本质: 通过比较中点元素与目标值的大小关系, 每次将搜索区间缩小到原来的一半。
     * 2. 循环条件与区间定义要一致: 常见两种写法 (闭区间 [left,right]) 和 (左闭右开 [left,right))。
     * 3. 防止 int 溢出: mid = left + (right - left) / 2 而不是 (left + right)/2。
     * 4. 有重复元素时, 基础二分返回“某一个”位置; 若需最左 / 最右, 需改写边界移动策略 (扩展: leftBound)。
     * 5. 退出循环后若没返回, 说明不存在 -> -1。
     * ------------------------------------------------------------
     * 常见错误点 (Pitfalls):
     * - while(left < right) 搭配闭区间更新会遗漏元素。
     * - mid 计算溢出。
     * - 更新边界时忘记 +1 / -1 导致死循环。
     * - 处理重复值需求与普通需求混淆。
     * ------------------------------------------------------------
     * ASCII 搜索过程示意 (nums = [1,4,7,11,15], target=11):
     * 初始: left=0, right=4
     * 迭代1: mid=2 -> nums[2]=7 < 11  => left=3
     * 迭代2: left=3, right=4, mid=3 -> nums[3]=11 命中 -> return 3
     * 指针变化:
     * idx:    0   1   2   3    4
     * 1   4   7  11   15
     * step1: [L---------M-----R]
     * step2:              [L-M--R]
     * ------------------------------------------------------------
     * 时间复杂度: O(log n)
     * 空间复杂度: O(1) (迭代) / O(log n) (递归调用栈)
     * ------------------------------------------------------------
     * 拓展: leftBound 用于找有序数组中第一个等于 target 的位置 (若不存在返回 -1)。
     */
    public int search(int[] nums, int target) {
        int left = 0;
        // 闭区间右端
        int right = nums.length - 1;
        // 区间不空
        while (left <= right) {
            // 防溢出写法: (left + right) >>> 1 也可; 这里选更加直观的 left + (right-left)/2
            int mid = left + (right - left) / 2;
            int midValue = nums[mid];
            if (midValue == target) {
                // 直接返回任一匹配位置
                return mid;
            } else if (midValue > target) {
                // 目标在左半部分 -> 缩小右边界
                right = mid - 1;
            } else {
                // midValue < target 目标在右半部分 -> 缩小左边界
                left = mid + 1;
            }
        }
        // 未找到
        return -1;
    }

    /**
     * 方法二: 递归实现 (演示用) - 实际使用时迭代更安全 (避免深栈)。
     */
    public int searchRecursive(int[] nums, int target) {
        return dfsBinary(nums, 0, nums.length - 1, target);
    }

    private int dfsBinary(int[] nums, int left, int right, int target) {
        if (left > right) {
            return -1; // 区间为空
        }
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        if (nums[mid] > target) return dfsBinary(nums, left, mid - 1, target);
        return dfsBinary(nums, mid + 1, right, target);
    }

    /**
     * 方法三 (扩展示例): 查找 target 第一次出现的位置 (左边界)
     * 若不存在返回 -1。适用于数组可能含重复值的场景。
     * 思路: 命中后不立即返回, 收缩右边界继续向左逼近。
     */
    public int leftBound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int ans = -1; // 记录最左命中位置
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midValue = nums[mid];
            if (midValue == target) {
                ans = mid;       // 记录
                right = mid - 1; // 继续向左找
            } else if (midValue > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    /**
     * 简单展示: 右边界 (最后一次出现) 可通过镜像思路实现。
     */
    public int rightBound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int ans = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midValue = nums[mid];
            if (midValue == target) {
                ans = mid;
                left = mid + 1;
            } else if (midValue > target) right = mid - 1;
            else left = mid + 1;
        }
        return ans;
    }

    // ========================== 测试入口 ==========================
    public static void main(String[] args) {
        S42_Easy_704_二分查找 solution = new S42_Easy_704_二分查找();
        System.out.println("=== 二分查找测试开始 ===");

        System.out.println("\n--- 测试1: 基本命中 (题目示例) ---");
        testBasicHit(solution);

        System.out.println("\n--- 测试2: 基本未命中 (题目示例) ---");
        testBasicMiss(solution);

        System.out.println("\n--- 测试3: 目标在首位 ---");
        testFirstElement(solution);

        System.out.println("\n--- 测试4: 目标在末位 ---");
        testLastElement(solution);

        System.out.println("\n--- 测试5: 单元素数组 ---");
        testSingleElement(solution);

        System.out.println("\n--- 测试6: 空数组 ---");
        testEmptyArray(solution);

        System.out.println("\n--- 测试7: 含重复值 - 验证左/右边界 ---");
        testWithDuplicates(solution);

        System.out.println("\n--- 测试8: 递归实现与迭代一致性 ---");
        testRecursiveConsistency(solution);

        System.out.println("\n--- 测试9: 随机数组多次验证 ---");
        testRandomized(solution);

        System.out.println("\n=== 所有测试完成 (若无断言失败则全部通过) ===");
    }

    // ========================== 测试用例实现 ==========================

    private static void testBasicHit(S42_Easy_704_二分查找 s) {
        int[] nums = {-1, 0, 3, 5, 9, 12};
        int target = 9;
        int idx = s.search(nums, target);
        System.out.println("返回下标: " + idx + " (期望: 4)");
        assert idx == 4 : "应返回4";
    }

    private static void testBasicMiss(S42_Easy_704_二分查找 s) {
        int[] nums = {-1, 0, 3, 5, 9, 12};
        int target = 2;
        int idx = s.search(nums, target);
        System.out.println("返回: " + idx + " (期望: -1)");
        assert idx == -1 : "应返回-1";
    }

    private static void testFirstElement(S42_Easy_704_二分查找 s) {
        int[] nums = {2, 4, 6, 8, 10};
        int idx = s.search(nums, 2);
        System.out.println("首元素下标: " + idx + " (期望: 0)");
        assert idx == 0 : "首元素应为0";
    }

    private static void testLastElement(S42_Easy_704_二分查找 s) {
        int[] nums = {2, 4, 6, 8, 10, 13, 17};
        int idx = s.search(nums, 17);
        System.out.println("末元素下标: " + idx + " (期望: 6)");
        assert idx == 6 : "末元素应为6";
    }

    private static void testSingleElement(S42_Easy_704_二分查找 s) {
        int[] a1 = {5};
        int hit = s.search(a1, 5);
        int miss = s.search(a1, 3);
        System.out.println("单元素命中: " + hit + " (期望: 0), 未命中: " + miss + " (期望:-1)");
        assert hit == 0 && miss == -1;
    }

    private static void testEmptyArray(S42_Easy_704_二分查找 s) {
        int[] empty = {};
        int idx = s.search(empty, 10);
        System.out.println("空数组返回: " + idx + " (期望:-1)");
        assert idx == -1;
    }

    private static void testWithDuplicates(S42_Easy_704_二分查找 s) {
        int[] nums = {1, 2, 2, 2, 3, 3, 4, 4, 4, 5};
        int left = s.leftBound(nums, 2);
        int right = s.rightBound(nums, 2);
        int any = s.search(nums, 2);
        System.out.println("2 的 leftBound=" + left + " (期望:1), rightBound=" + right + " (期望:3), 任意命中=" + any);
        assert left == 1 && right == 3 && any >= 1 && any <= 3;

        int leftMiss = s.leftBound(nums, 6);
        System.out.println("不存在的 6 -> leftBound=" + leftMiss + " (期望:-1)");
        assert leftMiss == -1;
    }

    private static void testRecursiveConsistency(S42_Easy_704_二分查找 s) {
        int[] nums = {-5, -3, -1, 0, 4, 9, 11, 18};
        for (int t : new int[]{-5, -1, 4, 18, 7}) {
            int i1 = s.search(nums, t);
            int i2 = s.searchRecursive(nums, t);
            assert i1 == i2 : "递归与迭代不一致 target=" + t + " i1=" + i1 + " i2=" + i2;
        }
        System.out.println("递归实现与迭代结果一致");
    }

    private static void testRandomized(S42_Easy_704_二分查找 s) {
        java.util.Random rand = new java.util.Random(42);
        for (int round = 0; round < 200; round++) {
            int n = 1 + rand.nextInt(50);
            int[] arr = new int[n];
            // 构造升序数组 (允许重复)
            int cur = rand.nextInt(5);
            for (int i = 0; i < n; i++) {
                cur += rand.nextInt(3); // 步长 0/1/2 -> 可重复
                arr[i] = cur;
            }
            // 选取若干随机目标 (含可能不存在的)
            for (int k = 0; k < 5; k++) {
                int pick;
                if (rand.nextBoolean()) {
                    // 取数组中的某个
                    pick = arr[rand.nextInt(n)];
                } else {
                    // 取一个附近可能不存在的值
                    pick = cur + rand.nextInt(3) + 1;
                }
                int idx = s.search(arr, pick);
                if (idx != -1) {
                    assert arr[idx] == pick : "返回位置不匹配";
                } else {
                    // 验证确实不存在
                    int left = s.leftBound(arr, pick);
                    assert left == -1 : "leftBound 应也为 -1, 实际=" + left;
                }
            }
        }
        System.out.println("随机 200 轮数组测试通过");
    }
}
